package com.platform.modules.alg.alglib.poj3237;

public class Poj3237 {
    public String output = "";
    private int maxn = 10010;
    int head[] = new int[maxn];//头结点
    int cnt = 0;
    int total = 0;
    int fa[] = new int[maxn]; // 父亲
    int dep[] = new int[maxn]; // 深度
    int size[] = new int[maxn]; // 子树结点总数
    int son[] = new int[maxn]; // 重儿子
    int top[] = new int[maxn]; // 所在重链顶端结点
    int id[] = new int[maxn];
    int rev[] = new int[maxn]; // u 对应的 dfs 序下标，下标对于的 u
    int Max;
    Edge1 a[] = new Edge1[maxn];
    edge e[] = new edge[maxn << 1];

    node tree[] = new node[maxn << 2];

    public String cal(String input) {
        int n;
        init();
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        for (int i = 1; i < n; i++) {
            String[] info = line[i].split(" ");
            a[i].u = Integer.parseInt(info[0]);
            a[i].v = Integer.parseInt(info[1]);
            a[i].w = Integer.parseInt(info[2]);
            add(a[i].u, a[i].v);
            add(a[i].v, a[i].u);
        }
        dep[1] = 1;
        dfs1(1, 0);
        dfs2(1, 1);
        build(1, 1, total); // 创建线段树
        for (int i = 1; i < n; i++) {
            if (dep[a[i].u] > dep[a[i].v]) {
                int temp = a[i].u;
                a[i].u = a[i].v;
                a[i].v = temp;
            }
            update(1, id[a[i].v], a[i].w);
        }
        String opt;
        int u, v;
        while (true) {
            String[] query = line[n++].split(" ");
            opt = query[0];
            if (opt.charAt(0) == 'D') break;
            u = Integer.parseInt(query[1]);
            v = Integer.parseInt(query[2]);
            if (opt.charAt(0) == 'Q') {
                Max = -0x3f3f3f3f;
                ask(u, v); // 查询 u->v 路径上边权的最大值
                output += Max + "\n";

            } else if (opt.charAt(0) == 'C')
                update(1, id[a[u].v], v); // 改变第 u 条边的值为 v
            else Negate(u, v); // 区间取反
        }
        return output;
    }

    public Poj3237() {
        for (int i = 0; i < a.length; i++) {
            a[i] = new Edge1();
        }
        for (int i = 0; i < e.length; i++) {
            e[i] = new edge();
        }
        for (int i = 0; i < tree.length; i++) {
            tree[i] = new node();
        }
    }

    void add(int u, int v) {
        e[++cnt].to = v;
        e[cnt].next = head[u];
        head[u] = cnt;
    }

    void init() {
        cnt = total = 0;
    }

    // 求 dep,fa,size,son
    void dfs1(int u, int f) {
        size[u] = 1;
        for (int i = head[u]; i > 0; i = e[i].next) {
            int v = e[i].to;
            if (v == f)//父节点
                continue;
            dep[v] = dep[u] + 1;//深度
            fa[v] = u;
            dfs1(v, u);
            size[u] += size[v];
            if (size[v] > size[son[u]])
                son[u] = v;
        }
    }

    // 求 top,id
    void dfs2(int u, int t) {
        top[u] = t;
        id[u] = ++total;//u对应的dfs序下标
        rev[total] = u;//dfs序下标对应的结点u
        if (son[u] == 0)
            return;
        dfs2(son[u], t);//沿着重儿子dfs
        for (int i = head[u]; i > 0; i = e[i].next) {
            int v = e[i].to;
            if (v != fa[u] && v != son[u])
                dfs2(v, v);
        }
    }

    // 初始化线段树,i 表示存储下标,区间 [l,r]
    void build(int i, int l, int r) {
        tree[i].l = l;
        tree[i].r = r;
        tree[i].Max = tree[i].Min = tree[i].lazy = 0;
        if (l == r) return;
        int mid = (l + r) / 2; // 划分点
        build(i << 1, l, mid);
        build((i << 1) | 1, mid + 1, r);
    }

    // 上传
    void push_up(int i) {
        tree[i].Max = Math.max(tree[i << 1].Max, tree[(i << 1) | 1].Max);
        tree[i].Min = Math.min(tree[i << 1].Min, tree[(i << 1) | 1].Min);
    }

    // 下传
    void push_down(int i) {
        if (tree[i].l == tree[i].r) return;
        if (tree[i].lazy == 1) { // 下传给左右孩子，懒标记清零
            tree[i << 1].Max = -tree[i << 1].Max;
            tree[i << 1].Min = -tree[i << 1].Min;
            int temp = tree[i << 1].Min;
            tree[i << 1].Min = tree[i << 1].Max;
            tree[i << 1].Max = temp;

            tree[(i << 1) | 1].Max = -tree[(i << 1) | 1].Max;
            tree[(i << 1) | 1].Min = -tree[(i << 1) | 1].Min;
            temp = tree[(i << 1) | 1].Max;
            tree[(i << 1) | 1].Max = tree[(i << 1) | 1].Min;
            tree[(i << 1) | 1].Min = temp;
            tree[i << 1].lazy ^= 1;
            tree[(i << 1) | 1].lazy ^= 1;
            tree[i].lazy = 0;
        }
    }

    // 点更新，线段树的第k个值为val
    void update(int i, int k, int val) {
        if (tree[i].l == k && tree[i].r == k) {
            tree[i].Max = val;
            tree[i].Min = val;
            tree[i].lazy = 0;
            return;
        }
        push_down(i);
        int mid = (tree[i].l + tree[i].r) / 2;
        if (k <= mid) update(i << 1, k, val);
        else update((i << 1) | 1, k, val);
        push_up(i);
    }

    // 区间更新，线段树的区间[l,r]取反
    void update2(int i, int l, int r) {
        if (tree[i].l >= l && tree[i].r <= r) {
            tree[i].Max = -tree[i].Max;
            tree[i].Min = -tree[i].Min;
            int temp = tree[i].Max;
            tree[i].Max = tree[i].Min;
            tree[i].Min = temp;
            tree[i].lazy ^= 1;
            return;
        }
        push_down(i);
        int mid = (tree[i].l + tree[i].r) / 2;
        if (l <= mid) update2(i << 1, l, r);
        if (r > mid) update2((i << 1) | 1, l, r);
        push_up(i);
    }

    // 查询线段树中[l,r]的最大值
    void query(int i, int l, int r) {
        if (tree[i].l >= l && tree[i].r <= r) { // 找到该区间
            Max = Math.max(Max, tree[i].Max);
            return;
        }
        push_down(i);
        int mid = (tree[i].l + tree[i].r) / 2;
        if (l <= mid) query(i << 1, l, r);
        if (r > mid) query((i << 1) | 1, l, r);
        push_up(i);
    }

    // 求 u,v之 间的最值
    void ask(int u, int v) {
        while (top[u] != top[v]) {//不在同一条重链上
            if (dep[top[u]] < dep[top[v]]) {
                int temp = u;
                u = v;
                v = temp;
            }

            query(1, id[top[u]], id[u]);//u顶端结点和u之间
            u = fa[top[u]];
        }
        if (u == v) return;
        if (dep[u] > dep[v]) {//在同一条重链上 ,//深度小的结点为u

            int temp = u;
            u = v;
            v = temp;
        }

        query(1, id[son[u]], id[v]);//注意是son[u]
    }

    // 把 u-v 路径上的边的值取相反数
    void Negate(int u, int v) {
        while (top[u] != top[v]) {//不在同一条重链上
            if (dep[top[u]] < dep[top[v]]) {
                int temp = u;
                u = v;
                v = temp;
            }
            update2(1, id[top[u]], id[u]);//u顶端结点和u之间
            u = fa[top[u]];
        }
        if (u == v) return;
        if (dep[u] > dep[v]) {//在同一条重链上,深度小的结点为u
            int temp = u;
            u = v;
            v = temp;
        }
        update2(1, id[son[u]], id[v]); // 注意是 son[u]
    }
}

class edge {
    int to, next;
}

class Edge1 {
    int u, v, w;
}

// 结点
class node {
    int l, r, Max, Min, lazy;//l,r区间左右端点，区间最值 ,懒标记
}
